package com.tianyuan.test2;

import java.util.*;

/**
 * 链表内指定区间反转
 * <p>
 * 将一个节点数为size链表m位置到n位置之间的区间反转，要求时间复杂度O（n)，空间复杂度O(1)。
 * 例如：
 * 给出的链表为1→2→>3→4→5→NULL,   m=2,n=4,
 * 返回1→4→3→2→5→>NULL.
 * 数据范围：链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足|val|≤1000
 */

public class Solution {
    /**
     * 反转链表中从第m个节点到第n个节点的部分
     *
     * @param head 链表头节点
     * @param m    起始位置（从1开始）
     * @param n    结束位置（从1开始）
     * @return 处理后的链表头节点
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        /**1. 初始化存储结构*/
        // 数组：存储前半段和反转后的区间节点
        ListNode[] nodes = new ListNode[n + 1];
        // 集合：存储区间外的后半段节点
        List<ListNode> list = new ArrayList<>();
        // 位置计数器（从1开始，标记当前节点是第几个）
        int loc = 1;


        /**2. 遍历链表，分类存储节点*/
        while (head != null) {  // 遍历所有节点
            if (loc < m) {  // 情况1：节点在反转区间之前（无需反转）
                nodes[loc] = head;  // 按原顺序存入数组（如m=2时，loc=1的节点直接存nodes[1]）
            } else if (loc >= m && loc <= n) {  // 情况2：节点在反转区间内（需要反转）
                // 关键逻辑：反转存储位置
                // 原位置loc → 数组位置 = n - (loc - m)
                // 例：m=2,n=4时，loc=2→4-0=4、loc=3→4-1=3、loc=4→4-2=2
                // 最终区间内节点在数组中顺序变为 [4,3,2]（实现反转）
                nodes[n - (loc - m)] = head;
            } else {  // 情况3：节点在反转区间之后（无需反转）
                list.add(head);  // 按原顺序存入集合
            }
            head = head.next;  // 移动到下一个节点
            loc++;  // 位置计数+1
        }

        /**3. 重新拼接链表*/
        head = new ListNode(-1);  // 创建虚拟头节点（简化头节点处理）
        ListNode r = head;  // 临时指针r，用于拼接节点
        // 第一步：拼接前半段和反转后的区间节点（数组中1~n位置）
        for (int i = 1; i <= n; i++) {
            r.next = nodes[i];  // 指针指向数组中的节点
            r = r.next;  // 指针后移
        }
        // 第二步：拼接区间后的节点（集合中的节点）
        for (ListNode node : list) {
            r.next = node;  // 指针指向集合中的节点
            r = r.next;  // 指针后移
        }
        r.next = null;  // 链表末尾置空（避免循环）
        return head.next;  // 返回新链表的实际头节点（虚拟头节点的下一个）
    }




    // 主方法：构建测试用例并运行
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例1：{1,2,3,4,5},2,4 → 预期{1,4,3,2,5}
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        ListNode result1 = solution.reverseBetween(head1, 2, 4);
        printList(result1);

        // 测试用例2：{5},1,1 → 预期{5}
        ListNode head2 = new ListNode(5);
        ListNode result2 = solution.reverseBetween(head2, 1, 1);
        printList(result2);

        // 测试用例3：{1,2,3,4},1,4 → 预期{4,3,2,1}
        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(2);
        head3.next.next = new ListNode(3);
        head3.next.next.next = new ListNode(4);
        ListNode result3 = solution.reverseBetween(head3, 1, 4);
        printList(result3);
    }

    // 辅助方法：打印链表（用于验证结果）
    private static void printList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        System.out.println(list);
    }
}